package com.leetcode.dynamic_programming;

import java.util.Arrays;

/**
 * @author Dennis Li
 * @date 2020/7/19 10:28
 */
public class CoinChange_322 {

    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        // 排序保证大的在后面
        Arrays.sort(coins);
        // 初识条件
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            // Integer.MAX_VALUE 再加一会变成负数
            dp[i] = Integer.MAX_VALUE - 1;
            // 由于coin数组的大小不定，因此要进行遍历
            for (int j = coins.length - 1; j >= 0; j--) {
                if (i >= coins[j]) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE - 1 ? -1 : dp[amount];
    }

    static class Solution {
        public int coinChange(int[] coins, int amount) {
            Arrays.sort(coins);
            int[] dp = new int[amount + 1];
            Arrays.fill(dp, Integer.MAX_VALUE - 1);
            dp[0] = 0;
            for (int i = coins.length - 1; i >= 0; i--) {
                int coin = coins[i];
                for (int j = coin; j <= amount; j++) {
                    dp[j] = Math.min(dp[j], dp[j - coin] + 1);
                }
            }
            return dp[amount] == Integer.MAX_VALUE - 1 ? -1 : dp[amount];
        }
    }

}
